package Tree;

import Sort.BubbleSort;
import Sort.QuickSort;

import java.util.regex.Pattern;

/**
 * @author yyq
 * @create 2021-11-06 14:25
 *
 * 创建哈夫曼树
 * 节点 数组 其中节点可能代表一个二叉树的根
 * 1 创建节点数组
 * 2 对节点数组进行排序
 * 3 选择最小的两个构成一个二叉树 并在加入节点数组
 * 4 重复上述步骤 直到数组长度唯一
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] a={13, 7, 8, 3, 29, 6, 1};
        TreeNode<Integer> root = constructHuffmanTree(a);
        BinaryTree.preOrder(root);

    }


    public static TreeNode<Integer> constructHuffmanTree(int[] a){
        int l=a.length;
        int[] temp = a.clone();
        BubbleSort.bubbleSort(temp);
        //构建节点数组
        TreeNode<Integer>[] treeNodes=new TreeNode[l];
        for (int i = 0; i < l; i++) {
            treeNodes[i]=new TreeNode<Integer>(temp[i]);
        }

        while (true){
            //只剩下最后两个节点时结束 手动合成即可
            if(l==2) {
                int data=treeNodes[0].data+treeNodes[1].data;
                TreeNode parent=new TreeNode(data);
                parent.left=treeNodes[0];
                parent.right=treeNodes[1];
                return parent;
            }
            //选择最小的两个进行合成
            int data=treeNodes[0].data+treeNodes[1].data;
            TreeNode parent=new TreeNode(data);
            parent.left=treeNodes[0];
            parent.right=treeNodes[1];
            //加入数组并进行排序
            insertTreeNodes(treeNodes,parent,l);
            l--;
        }

    }
    //将合成的新节点加入数组,加入后数组有序 此时0 1应该为无用项 它两刚刚合成成新的节点parent
    public static void insertTreeNodes(TreeNode<Integer>[] treeNodes,TreeNode<Integer> node,int l){
        //首先把所有的往前移一位
        for(int i=1;i<l-1;i++){
            treeNodes[i]=treeNodes[i+1];
        }
        //现在长度其实缩小到l-1 边比较边移动
        for (int i = 1; i < l-1; i++) {
            //如果node比后面的节点大，后面的节点向前平移
            if(node.data>treeNodes[i].data){
                treeNodes[i-1]=treeNodes[i];
            }
            //如果node比后面的节点小 直接插入即可
            if(node.data<=treeNodes[i].data){
                treeNodes[i-1]=node;
                break;
            }
            //它是最大值 放在末尾
            if(i==l-2){
                treeNodes[l-2]=node;
            }
        }


    }
}
